package dfs;

/**
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 *
 * 岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上相邻。
 * 你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 *
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 *
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0
 *
 * 限制：
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 50
 * grid[i][j] 为 0 或 1
 */

public class MaxAreaOfIsland_695 {
    private int maxArea = 0;

    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
//                    dfs(grid, i, j, m, n, 0);
                    res = Math.max(res, dfs2(grid, i, j, m, n));
                }
            }
        }

        return res;
    }

    // 错误，假设遍历到了一个岛屿的中心，只能一个最大分支的岛屿数，而不是全部岛屿数
    private void dfs(int[][] grid, int i, int j, int m, int n, int area) {
        if (area > maxArea) {
            maxArea = area;
            System.out.println("i: " + i + " j: " + j + " before area: " + area + " maxArea: " + maxArea);

        }

        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }

        if (grid[i][j] == 0) {
            return;
        }

        System.out.println("i: " + i + " j: " + j + " after area: " + area + " maxArea: " + maxArea);
        grid[i][j] = 0;
        dfs(grid, i + 1, j, m, n, area + 1);
        dfs(grid, i - 1, j, m, n, area + 1);
        dfs(grid, i, j + 1, m, n, area + 1);
        dfs(grid, i, j - 1, m, n, area + 1);
    }

    private int dfs2(int[][] grid, int i, int j, int m, int n) {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return 0;
        }

        if (grid[i][j] == 0) {
            return 0;
        }

        grid[i][j] = 0;
        // 将周围的所有岛屿统计在内，而不是某一个分支
        int count = 1;
        count += dfs2(grid, i + 1, j, m, n);
        count += dfs2(grid, i - 1, j, m, n);
        count += dfs2(grid, i, j + 1, m, n);
        count += dfs2(grid, i, j - 1, m, n);
        return count;
    }
}
